int f[N];
void init() {
    f[0] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 1; ; j++) {
            int t1 = i - j * (3 * j - 1) / 2;
            int t2 = i - j * (3 * j + 1) / 2;
            int flag;
            if (j&1) flag = 1;
            ese flag = -1;
            if (t1 < 0 && t2 < 0) break;
            if (t1 >= 0) f[i] = (f[i] + flag * f[t1]) % MOD;
            if (t2 >= 0) f[i] = (f[i] + flag * f[t2]) % MOD;
        }
        f[i] = (f[i] + MOD) % MOD;
    }
}
int get(int n, int k) {//a number use no more than k times
    int ans = f[n], flag = -1;
    for (int i = 1; ; i++) {
        int t1 = k * i * (i * 3 - 1) / 2;
        int t2 = k * i * (i * 3 + 1) / 2;
        if (t1 > n && t2 > n) break;
        if (t1 <= n) ans = (ans + flag * f[n - t1]) % MOD;
        if (t2 <= n) ans = (ans + flag * f[n - t2]) % MOD;
        flag = -flag;
    }
    return (ans + MOD) % MOD;
}
